package sort;

public class MergeSort {

	public static void main(String[] args) {
//		int[] a = { 6};
//		int[] b = { 5};
//		int[] c = new int[a.length + b.length];
//		merge(c, a, b, a.length, b.length);
//		for (int i : c) {
//			System.out.print(i + " ");
//		}
		int[] a = { 7, 6, 2, 15, 1, 3, 5, 11, 10, 2, 18, 9, 10, 19, 23, 20, 26,
				54, 34 };
		mergeSort(a);
		//merge(a, 2, 4, 9);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	//非递归归并
	public static void mergeSort(int[] t) {
		if (t == null || t.length <= 1)
			return;
		// len为排好序的长度
		int len = 1;
		// 程序边界的处理非常重要
		while (len <= t.length) {
			//len * 2是这次排序的长度，比如刚开始是排序1 2； 3 4；此时len 为1
			//之后是排序1 2 3 4 ； 5 6 7 8；....此时len为2
			for (int i = 0; i + len <= t.length - 1; i += len * 2) {
				// len表示初始排好序的长度，由于初始只有一个数是排好序的，故len=1
				// 对于mid，mid-low+1=len；故mid=len-1+low；
				int low = i, mid = i + len - 1, high = i + len * 2 - 1;
				// 如果high大于边界了，就只取到边界的值就行
				if (high > t.length - 1){
					high = t.length - 1;
				}
				merge(t, low, mid, high);
				System.out.println(low + " " + mid + " " + high);
				for (int j : t) {
					System.out.print(j + " ");
				}
				System.out.println();
			}
			// 排好序的子序列的长度加倍
			len *= 2;
		}
	}

	// 对数组nums作归并递归排序
	//low表示第一个排序的序列的起始下标，mid为第一个排序的序列的终点下标
	//high表示第二个排序序列的起始下标
	public static void merge(int[] nums, int low, int mid, int high) {
		int[] temp = new int[high - low + 1];
		int i = low;// 左指针
		int j = mid + 1;// 右指针
		int k = 0;
		// 按照顺序把数先移到新数组中
		// 其中的选择语句相当于c[k++] = a[i] < b[j] ? a[i++] : b[j++];
		while (i <= mid && j <= high) {
			if (nums[i] < nums[j]) {
				temp[k++] = nums[i++];
			} else {
				temp[k++] = nums[j++];
			}
		}
		// 把左边剩余的数移入数组
		while (i <= mid) {
			temp[k++] = nums[i++];
		}
		// 把右边边剩余的数移入数组
		while (j <= high) {
			temp[k++] = nums[j++];
		}
		// 由于起始下标可能不是0，故从low开始，将temp中的数据赋给nums
		for (int k2 = 0; k2 < temp.length; k2++) {
			nums[k2 + low] = temp[k2];
		}
	}

	// 合并两个有序数组
	public static void merge(int[] c, int[] a, int[] b, int n, int m) {
		int i, j, k;
		for (i = 0, j = 0, k = 0; k < n + m; k++) {
			if (i == n && j < m) {
				c[k] = b[j];
				j++;
				continue;
			}
			if (j == m && i < n) {
				c[k] = a[i];
				i++;
				continue;
			}
			c[k] = a[i] < b[j] ? a[i++] : b[j++];
		}
	}
}
